package com.lw.leetcode.str.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 140. 单词拆分 II
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/21 9:40
 */
public class WordBreak140 {

    public static void main(String[] args) {
        WordBreak140 test = new WordBreak140();

        // ["cats and dog","cat sand dog"]
//        String str = "catsanddog";
//        List<String> list = Arrays.asList("cat", "cats", "and", "sand", "dog");

        // ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
//        String str = "pineapplepenapple";
//        List<String> list = Arrays.asList("apple", "pen", "applepen", "pine", "pineapple");

        // []
        String str = "catsandog";
        List<String> list = Arrays.asList("cats", "dog", "sand", "and", "cat");

        List<String> list1 = test.wordBreak(str, list);
        System.out.println(list1);

    }


    public List<String> wordBreak(String s, List<String> wordDict) {
        int length = s.length();
        Set<String> set = new HashSet<>(wordDict);
        List<String>[] arr = new ArrayList[length];
        for (int i = 0; i < length; i++) {
            arr[i] = new ArrayList<>();
        }
        for (int i = 1; i <= length; i++) {
            List<String> list = arr[i - 1];
            for (int j = Math.max(0, i - 10); j < i; j++) {
                String v = s.substring(j, i);
                if (set.contains(v)) {
                    if (j == 0) {
                        list.add(v);
                    } else {
                        for (String s1 : arr[j - 1]) {
                            list.add(s1 + " " + v);
                        }
                    }
                }

            }
        }
        return arr[length - 1];
    }

}
